#include <vector>
#include <algorithm>
using namespace std;
/*
 * @lc app=leetcode.cn id=135 lang=cpp
 *
 * [135] 分发糖果
 */

// @lc code=start
int dx[] = {-1, 1};
class Solution {
public:

    
    int candy(vector<int>& ratings) {
        int res = 0;
        vector<int> dp(ratings.size(), 0);
        for (int i = 0; i < ratings.size(); i++) {
            if (!dp[i]) dfs(i, ratings, dp);
            res += dp[i];
        }
        return res;
    }

    int dfs(int index, vector<int> & rating, vector<int> & dp) {
        if (dp[index]) return dp[index];  
        bool flag = false; int candy = 0;
        for (int i = 0; i < 2; i++) {
            int nx = index + dx[i];
            if (nx >= 0 && nx < rating.size()) {
                if (rating[index] > rating[nx]) {
                    candy = max(candy, dfs(nx, rating, dp) + 1);
                    flag = true;
                }
            }
        }
        if (!flag) return dp[index] = 1;
        return dp[index] = candy;
    }
};
// @lc code=end

